package _10_图;

import java.util.*;

public class _1436_旅行终点站 {

    // HashSet保存城市A
    // 查看城市B是否存在城市A中
    public String destCity(List<List<String>> paths) {
        Set<String> set = new HashSet<>();
        for (List<String> path : paths) {
            set.add(path.get(0));
        }
        for (List<String> path : paths) {
            if (!set.contains(path.get(1))) {
                return path.get(1);
            }
        }
        return null;
    }

    // Hash表保存映射
    public String destCity1(List<List<String>> paths) {
        Map<String, String> pathMap = new HashMap<>();
        for (List<String> path : paths) {
            pathMap.put(path.get(0), path.get(1));
        }
        String start = paths.get(0).get(1);
        while (true) {
            String endPath = pathMap.get(start);
            if (endPath == null) {
                break;
            }
            start = endPath;
        }
        return start;
    }

}
